package 栈和队列.前K个高频元素;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/29 20:29
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array = {1,1,1,2,2,3,3,3,3};
        int k = 2;
        int[] ints = topKFrequent2(array, k);
        System.out.println(ints.toString()  );
    }


    //哈希表
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        List<Integer> list = new ArrayList<>();
        //按照value排序
        LinkedHashMap<Integer, Integer> hashMap = map.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (c1, c2) -> c1, LinkedHashMap::new));
        //hashMap = map.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue,(c1,c2) -> c1,LinkedHashMap::new));
        Set<Integer> set = hashMap.keySet();
        Iterator<Integer> iterator = set.iterator();
        int i = 0;
        while (iterator.hasNext() && i < k){
            Integer next = iterator.next();
            list.add(next);
            i++;
        }
        //    String[] strs = list.toArray(new String[list.size()]);
        //list转数组  对于int ，char，由于它们不是类，所以需要使用包装类Integer和Character，或者stream转换
        int[] array = list.stream().mapToInt(Integer::valueOf).toArray();
        return array;
    }


    //使用优先队列构建堆 大佬解法  其实也就是堆排序 海量数据中找出前K个最小的元素
    public static int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
        queue.addAll(map.entrySet());
        int[] ans = new int[k];
        for (int i = 0; i < k && !queue.isEmpty(); i++){
            ans[i] = queue.poll().getKey();
        }
        return ans;
    }
}
